package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode0647 
* @author      : ganwei 
* @date        : 2020年5月24日 
* @Description : 647. 回文子串 
*/
public class Leetcode0647 {
    int result = 0;
	/**
     * -解题思路,暴力算法，竟然也可以提交成功
     */
	public int countSubstrings(String s) {
		int result = 0;
		for(int i = 0; i < s.length(); i++) {
			for(int j = i; j < s.length(); j++) {
				if(isPalindrome(s.substring(i, j+1))) {
					result++;
				}
			}
		}
		
		return result;
    }
	
	/**
	 * -动态规划
	 */
	public int countSubstrings_1(String s) {
        // 动态规划法
        boolean[][] dp = new boolean[s.length()][s.length()];
        int result = 0;
//
//        for (int j = 0; j < s.length(); j++) {
//            for (int i = 0; i <= j; i++) {
//                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
//                    dp[i][j] = true;
//                    result++;
//                }
//            }
//        }
        
        for(int i = 0; i < s.length(); i++) {
        	for(int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    result++;
                }        		
        	}
        }
        
		return result;
	}
	
	/**
	 * -判断字符串的子串是否为子串
	 */
	public boolean isPalindrome(String substr) {
		int start = 0;
		int end = substr.length()-1;
		while(start <= end) {
			if(substr.charAt(start) != substr.charAt(end)) {
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
	
	
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		Leetcode0647 l0647 = new Leetcode0647();
		String ss = "abc";
		
		System.out.println(l0647.countSubstrings(ss));
	}
    
}
